package leetcode.hash;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * 详解： Map 运用
 * <p>
 * 来源：https://leetcode.cn/problems/two-sum/
 * <p>
 * 给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
 * <p>
 * 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
 * <p>
 * 示例:
 * <p>
 * 给定 nums = [2, 7, 11, 15], target = 9
 * <p>
 * 因为 nums[0] + nums[1] = 2 + 7 = 9
 * <p>
 * 所以返回 [0, 1]
 */
public class L0001 {

    public static void main(String[] args) {


        int[] nums = {2, 7, 11, 15};
        int target = 9;

        int[] ret = towSum(nums, target);
        System.out.println(Arrays.toString(ret));


        String s = "saebe";
        String t = "saebe";
        System.out.printf("结果位" + isAnagram(s, t));
    }


    /**
     * 两个数求和
     *
     * @param nums   原数组集合
     * @param target 目标只
     * @return 坐标位置
     *
     * 时间复杂度O(n) ，空间复杂度 O(1) 常量
     */
    private static int[] towSum(int[] nums, int target) {
        // 常规方法：for嵌套 循环遍历，但是元素使用了两次
        int[] ret = new int[2];
        Map<Integer, Integer> map = new HashMap<>();

        for (int i = 0; i < nums.length; i++) {
            int tmp = nums[i];
            int other = target - tmp;
            if (map.containsKey(other)) {
                ret[0] = i;
                ret[i] = map.get(other);
                break;
            }
            map.put(tmp, i);
        }

        return ret;

    }

    /**
     * 讲解：出现1次字母加1，另一个字符串字母出现1次，则减1
     * 时间复杂度O(m+n) 空间复杂度O(1)  26个字母
     * 判断两个字母是否为异位词  （字母个数相同，但是单词不同）  假设字母都为下写
     *
     * @param s 字符串s
     * @param t 字符串t
     * @return 是否相同
     */
    private static boolean isAnagram(String s, String t) {

        // 如果为空，或者字符串内容相同
        if (s == null || t == null || s.equals(t)) {
            return false;
        }

        // 假设全是小写字母    --> 如果位大写字母，则26 + 6 + 26 及58 大写字母与小写字母之间包含6个特殊字符  int[] ret = new int[58]; 减去 'A'
        int[] ret = new int[26];
        for (int i = 0; i < s.length(); i++) {
            ret[s.charAt(i) - 'a']++;
        }


        for (int i = 0; i < t.length(); i++) {
            ret[t.charAt(i) - 'a']--;
        }

        //是否存在非0的数据
        for (int count : ret) {
            if (count != 0) {
                return false;
            }
        }
        return true;
    }
}
